Not Applicable
This invention relates to the field of computer-implemented systems and methods for extracting and displaying implicit associations among items in loosely-structured data sets.
The advent of electronic data storage and retrieval technology has provided users of that technology with significant benefits in terms of the ability to request and receive enormous amounts of information with very little effort and in a very short period of time. Associated with these advance, however, is the difficulty in identifying information that is relevant to the searcher""s notion of what he wants to find, and separating that information from the sheer volume of data retrieved which is not relevant to those concerns. This issue is familiar to anyone who has used one of the common search tools to search the worldwide web for information: potentially thousands of pages of information are returned, but there is almost no assistance in identifying which are relevant to the searcher""s interests, and which are not.
People are increasingly surrounded, if not bombarded, with a growing volume of data and information. Gaining access to data is relatively easy; being able to sort through that data to find information relevant to our interests is increasingly difficult. One general approach to this problem has been to attempt to narrow search results by filtering out items deemed irrelevant to the searcher""s interests. The purpose of data set search mechanism, such as Standardized Query Language (SQL) inquiries for formally structured databases, or search xe2x80x9cenginesxe2x80x9d such as those used by popular Internet sites, is to return a subset of the total data set based on the specifications supplied by the person making the query. The usefulness of these search mechanisms, depends to a large extend on the knowledge and sophistication of the person making the query: if the query is formed using the same terminology used to describe or index the data source (of course this is required in the SQL query example), the greater is the probability that the query will return xe2x80x9crelevantxe2x80x9d information. The less the searcher knows about the structure or specific terminology describing the data set being queried, the greater the volume of irrelevant information that will be retrieved.
However, the capability of judging what the searcher""s actual intentions and interests are, in the context of an automated search system such as a computer search algorithm, is highly problematic. This is especially difficult when the searcher""s intentions are vague or uncertain, which leads to search criteria that are ill-defined and ambiguous. This is a well-known and unsolved problem in the field of data search and retrieval. Natural languages, such as English, are comprised of numerous words and expressions capable of conveying multiple meanings, the intended meaning of which is often recognizable only when the ambiguous term is considered in context with other surrounding terms and conceptual constructs. To compound the problem, the searcher may not realize what he is looking for, and may recognize relevant data only when he sees it in a context that he could not have specified in advance. One common strategy in defining the context that will lead to relevant information, is to interpret the searcher""s intentions by filtering out assumed irrelevant data based on that interpretation. However, solutions based on such interpretations of the searcher""s intent may fall short of delivering relevant data, especially when the query itself is uncertain and not fully defined.
The identification of items in a data set can be facilitated by imposing a categorical structure on that data, which is another general strategy that has been applied to the problem of producing relevant search results. A number of Internet search engines use this approach, grouping results in terms of such categories as xe2x80x9cmusic,xe2x80x9d xe2x80x9ctravel,xe2x80x9d xe2x80x9cshopping,xe2x80x9d and so on. This approach, although arguably more useful than most attempts to discern the searcher""s underlying intentions, has numerous problems. Sorting data items into determined and fixed categories generally requires human intervention and interpretation; that is, the process is expensive and not easily automated. Also, data items frequently fall into multiple categories: how are they to be represented? There can be many alternate interpretations of what belongs in one category and what does not, and this added to the ambiguity of language itself means that imposing an external categorical structure on a complex data set is difficult, costly, inexact, and generally incomplete. Last and not least, the relationships between the categories themselves cannot be easily conveyed to the searcher. There is a relationship between, for example, all xe2x80x9ccountriesxe2x80x9d and all xe2x80x9cvegetation,xe2x80x9d but this type of relationship cannot be described in a fixed category, xe2x80x9clist-likexe2x80x9d format typical of popular Internet search engines.
Consider a simple example: a person is visiting a city which he has not visited in many years. The person has a vague memory of a wonderful restaurant where he dined with friends long ago: he has no idea where it is, what the name might be, but he does recall that it had an ornately carved wooden bar made of South American rosewood, and that the cuisine was an interesting combination of Italian and Asian, although he cannot remember if it was Thai or Vietnamese, or possible Chinese. To find it again, he might look in the hardcopy telephone Yellow Pages, or access an electronic yellow pages.
Use of the hardcopy Yellow Pages requires that the person run down the entire alphabetical list of restaurant names, hoping to remember the name itself, or he may be able to browse through a categorical listing of xe2x80x9cItalianxe2x80x9d as opposed to xe2x80x9cChinesexe2x80x9d restaurants. His chance of finding the information he wants, namely the name of the restaurant, depends on his ability to xe2x80x9crecognizexe2x80x9d that name when he sees it.
Online, using a Web-based yellow pages, he can specify a Boolean search, using terms such as xe2x80x9cItalian AND Asian,xe2x80x9d which may return a large list of restaurants, from midtown to the farthest suburban outpost, and offering many combinations of cuisine. The restaurant he is looking for may be in this list somewhere, but again, not obviously so. The only hope he has of finding it is to painstakingly work down the list, and perhaps go to individual restaurant Web sites, reading the descriptions and looking at the pictures. Still, even though he is not exactly sure of what he is looking for, if he located a reference to an Italian-Asian cuisine restaurant which mentioned an ornately carved antique rosewood bar, he would feel relatively confident about having found what he was looking for.
What would be preferred in this situation is a more detailed category, and at the same time a more semantically flexible category, to describe something close to what he is looking for: Italian-Asian-possibly-Vietnamese restaurants with antique carved-Rosewood-bars. Attempting to express this type of dynamic, subjectively-relevant categorization, through the use of fixed, hierarchical category schemes is problematic at best, and virtually impossible in terms of anticipating all the combinations of categorical constructs possible. An ideal solution to the problem would be a query result, based not on externally defined categories, or on categories which may be specified in the search itself, but a query result based on the categories inherent (implicit) in the data set, and based on the content and descriptions of the individual data items, no matter what that content might be.
To stretch the above example, suppose the restaurant the person is looking for is actually run by a Greek-Cambodian couple, and thus the cuisine is off the mark of his original search criteria And, that he had forgotten that it is furnished with chairs from the Captain""s table of an old whaling ship. He did not specify this in his search, but if he sees xe2x80x9cshipxe2x80x9d or xe2x80x9cCaptain""s tablexe2x80x9d as an inherent categorical element in one of the returned data items, his memory might be jogged into recognizing that this is the restaurant he is looking for.
Actual success in finding what one is looking for may depend on seeing a broader set of associations within the targeted data set. The way people recognize and understand something is largely based on its context, and on the relationship and proximity to other things they perceive as being associated with it. The silhouette of a crowd in a photograph, for example, might be a crowd of people anywhere; however, if the view includes an outline of the Eiffel Tower in the background, one is instantly oriented to the context of the scene, including all the connotative implications of such a scene based on the viewer""s knowledge and presumptions about it.
The sense of context one gets from comparing and contrasting the items in a data set to each other facilitates one""s recognition and understanding of those data items. Without the ability to discern relational context within a data set, it is difficult for a searcher to focus on those specific areas of the entire data set which are most closely related to his or her subjective intentions. It is also difficult for the searcher to get a sense of the semantic breadth of the data set as represented by its most divergent items. The strength of the relationships or associations among items in a group provides a context which facilitates one""s cognitive recognition of those data items themselves. In this sense, the capability of presenting a data set in a comprehensive relational context, independent of the searcher""s search criteria, where the searcher can perceive associations between data items and between groups of data items, facilitates the ability to recognize those data items and relationships that are subjectively relevant. Existing Web search engines and methods convey this type of relational information very poorly, if at all.
One very general approach that has been applied toward representing context or relevance in data sets has been to collect a measure of similarity among all data items and then to use those measurements to calculate Euclidean xe2x80x9cdistancesxe2x80x9d between all objects which correspond to the perceived similarities between the data items. Although a number of mathematical techniques can be used to produce a schema in which associations between data items are represented as distances in an n-dimensional space, all such methods have as their basis the linear- or matrix-algebra decomposition of an input matrix consisting of data items, each of which has a value indicating the strength of its association to other data items according to some set of measuring criteria. As noted in the review below of methods in related art references which use Euclidean distances to represent associations in data sets, most are concerned with focused search and retrieval methods that have serious limitations in terms of portraying relational context in the data set. Given a profile, or set of values of the same type as the original measurements which produced the Euclidean distances between data items, a very specific set of data items can be identified and retrieved from the total data set. Such techniques can offer the possibility of retrieving data items which are xe2x80x9cclose toxe2x80x9d the searcher""s target data items in terms of Euclidean distance, though such items may not be exact matches. The methods in the reviewed references, however, suffer from limitations in that they require additional input from the searcher in terms of creating a xe2x80x9csearch profile,xe2x80x9d or they require a xe2x80x9ctraining setxe2x80x9d of documents or text passages similar to the items being searched for. Each of these methods still attempts to filter or reduce the data set by eliminating items deemed to be irrelevant to the search, and therefore provides an overly restrictive sampling of the data in terms of context. The criteria used to create the measurements of similarity in these examples are not relevant to the conceptual content and meaning of the data set. For example, the similarity of two or more documents may be compared based on measurements of how frequently the words in those documents are used in the English language. This produces a uniform measure which can be used to indicate some kind of similarity or dissimilarity among the documents, but it tells one nothing about the conceptual structure of the data set as determined by the contents of documents themselves. In addition, these methods require extensive pre-indexing or pre-processing of the target data set, in that similarity measures must be calculated among all items in the target set, not just the subset of interest to the searcher, prior to the search. Although such indexing could be done once for an entire data set, there is a high processing cost associated with this kind of pre-indexing. More realistically, because data sets in the real world are dynamically growing and changing on a continual basis, re-indexing of the data set is a continual requirement which carries a high overhead cost. Thus, the methods reviewed below offer no provision for representing the kind of information for which there is a recognized need: that is, for providing a contextual overview of the unstructured, frequently-changing data set or subset, in which the strengths of associations among the data items are apparent, in which those associations are based on the actual conceptual nature of the data items themselves, and in which the concepts which create the associational structure are visible and apparent to the searcher.
One way to convey such conceptual-associational-relational information in a data set, or part of a data set, is to show it, that is, to present the data items in a visual plot or graph such that the distance between data points represents some measure of strength of association between those data points. The Euclidean distance approach toward data set representation allows this type of visual presentation. The result is a plot or graph in which like items will cluster visually with other like items, and further away from dissimilar items, and the groups or clusters of items which are thus formed will also do the same: groups of similar items tend to cluster together and clusters of dissimilar items tend to lie at opposite ends of the plot. This can facilitate the viewer""s perception of overall patterns and structure in the data space. In addition, the ability to convey strength-of-association information about a data set helps to disambiguate the searcher""s intentions, particularly when those intentions are vaguely formulated or when the terminology used to frame the intentions are ambiguous. Suppose, for example, the searcher is looking in the data set for instances of the word xe2x80x9cplant.xe2x80x9d Is that xe2x80x9cplantxe2x80x9d as in xe2x80x9cvegetationxe2x80x9d, or xe2x80x9cplantxe2x80x9d as in xe2x80x9cto sowxe2x80x9d, or xe2x80x9cplantxe2x80x9d as in xe2x80x9cmanufacturing plant?xe2x80x9d In fact, instances of all three uses of the word could be in the data set. If one could view a visual map of the relationships in the set, or part of the set, one might be able to recognize familiar items which would give one clues as to which instance of xe2x80x9cplantxe2x80x9d one is really interested. For example, a datum instance labeled xe2x80x9cplantxe2x80x9d in close proximity to one labeled xe2x80x9cbuildingxe2x80x9d, and a datum instance labeled xe2x80x9cplantxe2x80x9d in close proximity to one labeled xe2x80x9ctreexe2x80x9d or xe2x80x9crootxe2x80x9d or xe2x80x9cfarmerxe2x80x9d, gives one cognitive clues about the actual meaning of each instance of the ambiguous label xe2x80x9cplantxe2x80x9d. The ability to view the data set all at once, and to see associations between items based on the visual phenomena of clustering and distance, allows the viewer to form cognitive categories which are subjectively relevant, and to help to organize and lend familiarity and structure to the data set as a whole. It can be argued that the observer himself or herself best determines what is subjectively relevant, and the capability of presenting the data set in a comprehensive relational context, where the observer can see associations between data items and between groups of data items, facilitates the observer""s ability to recognize in the data set that which is subjectively relevant and that which is not.
Some of the methods in the references reviewed below are somewhat related to this general issue in that they take the approach of plotting similarities between data items as distances in Euclidean space. Each of these methods is limited by exhibiting one or more of the undesirable characteristics previously discussed, for example, by requiring pre-indexing of the target data set, or by requiring a search profile, or by requiring extensive input on the part of the searcher. In addition, each lacks one or more of the following desirable characteristics: (1) the ability to automatically categorize the data based on the conceptual content of the items in the data set, in other words, to let the data categorize themselves (2) the use of similarity measures which reflect the nature and content of the data set itself, and (3) the ability to display the full range of relationships in the data set, that is, to display not only individual data items in the visual plot, but also to display the underlying concepts which bind various members of the data set together, and, in addition, to display the strength of relationships between those concepts in the whole data space.
A variety of solutions to the problem of information overload have been proposed in the related art. The limitations of background art in the patent literature and in the non-patent literature are described below. The U.S. patents identified by number below are incorporated in this disclosure by reference as if they were set out in full herein.
Deerwester et al. (U.S. Pat. No. 4,839,853) and Deewester et al. (U.S. Pat. No. 5,778,363) disclose methodologies for revealing information structures in collections of data items, and identifying structure, such as associative structure, in such a set. Part of the described methodologies involves cross correlation of two or more sets of data and the calculation of distance and similarity measures using, in part, singular value decomposition. Thus, these search retrieval methodologies are limited in that they require some type of pre-indexing of the data set. The user of the methodologies must construct a query vector consisting of pairs of attribute identifiers and scalar values. The attribute identifiers must be from the same set of terms used to pre-index the target data set. Given a query vector consisting of attribute items, the methods return related data items; conversely, given a query vector consisting of data items, the methods return related attribute items. The methods are limited in that they are incapable of accomplishing both tasks simultaneously. In addition, these references disclose search and retrieval methodologies, not methodologies whose object is to represent associations between objects in a data set and their inherent conceptual descriptions. Moreover, there is no provision for plotting the data set or for revealing relationships in the data set other than those between the query profile and the subset of returned results.
Gallant (U.S. Pat. No. 5,325,298) discloses a method for generating context vectors for a plurality of word stems to be used in a search and retrieval system. Context vectors are based on the relationship of a given word to a fixed set of other words. A summary vector for a document is created based on the context vectors of all non-noise words in the document. Searching for relevant documents is accomplished by converting a user inquiry into a query vector which is compared to the summary vectors of a set of documents. The method is limited in that it requires extensive preprocessing of the target data set and preprocessing of a user query. Measures of relationships between documents are indirectly based on the relationships of individual words in the documents to an arbitrarily chosen set of criterion words.
Hutson (U.S. Pat. No. 5,559,940) and Hutson (U.S. Pat. No. 5,761,685) disclose a multi-dimensional text search, retrieval, and display system. Textual data is converted into a two-dimensional matrix and analyzed by means of a single value decomposition (SVD) technique to decompose the matrix into its lexical, semantic and/or textual structures. Extensive pre-processing of the target data set is required. Similarity measures are based on the translation of sentences into standard syntactic structure with a subsequent rating. A query profile is required of the user of the methodology; the results are a filtered subset of data items deemed relevant to the user""s subjective intentions. The results are represented in a three-dimensional cube, similar to a stack of documents. An historical database of associations is required for the optimal functioning of the method.
Caid et al. (U.S. Pat. No. 5,619,709) and Caid et al. (U.S. Pat. No. 5,794,178) disclose a system and method for generating context vectors for use in storage and retrieval of documents and in visualizing of information using graphical representations of context vector based relationships. The context vector generation scheme is limited in that it relies on a processing-intensive neural network operating on a training corpus of records. The resulting vectors are relationship based, formed by the proximity of words to one another. A learning law is used, employing a technique of xe2x80x9cwindowed co-occurrencexe2x80x9d wherein a fixed-size moving window is applied throughout the document, and words within the window may exert xe2x80x9cinfluencexe2x80x9d on neighboring words in accordance with pre-determined measures of mutual co-importance. The results of the method can be displayed in a simulated three-dimensional space, but the method is limited in that data items cluster in proximity to axes projected through the space. The axes represent the query terms of the user of the method. The method is further limited in that no attempt is made at further categorization of the returned set of data items, nor are other conceptual relationships between the data items revealed or represented, other than that they are all related to the user""s query terms in some way.
Egger et al. (U.S. Pat. No. 5,832,494) disclose a computer-implemented research tool for indexing, searching and displaying data. Text objects are indexed by creating a numerical representation of the data using an indexing technique called xe2x80x9cproximity indexing.xe2x80x9d The technique is used to find the relations, patterns and similarity among the data using statistical techniques and empirically-generated algorithms. This invention is limited to analyzing the relevance of text objects to a selected object and cannot be used to analyze the associations among all objects in a database. In one embodiment of the invention, xe2x80x9ccase lawxe2x80x9d text objects are analyzed for the presence of one or more of eighteen specific patterns (e.g., xe2x80x9cB cites Axe2x80x9d) that are alleged to xe2x80x9ccapture most of the useful information in a cross-referenced databasexe2x80x9d). A xe2x80x9ccoefficient of similarityxe2x80x9d is calculated by a xe2x80x9csimilarity routinexe2x80x9d that operates on a xe2x80x9cproximity matrix that contains xe2x80x9ccolumn vectorsxe2x80x9d that represent the relationship between a selected case and every other case in the database. One step in the calculation involves determining the absolute Euclidean distance between a selected column and the other columns in the matrix. In another embodiment, a xe2x80x9cSemantical Clustering of a Boolean Index Routinexe2x80x9d is used to index text objects according to the similarity of phrases and words contained within each text object in the database. Clustering algorithms from Hartigan, J. A. Clustering Algorithms, New York: John Wiley and Sons, Inc., 1975 are used which differ from the dual-scaling algorithms used to implement the present invention. In yet another embodiment, case law textual objects are organized in a xe2x80x9cconceptual spacexe2x80x9d in which xe2x80x9cdegree of similarityxe2x80x9d is represented on a vertical (xe2x80x9cYxe2x80x9d) axis and publication date is represented on a horizontal axis (xe2x80x9cXxe2x80x9d). The degree of similarity is a measure of the topical relatedness of text objects from a pool of such objects to one or more selected text objects (e.g., a particular court decision or web page). In a preferred embodiment, the xe2x80x9cdepthxe2x80x9d of the object in the xe2x80x9cZxe2x80x9d dimension is used to convey additional information to the user (e.g., xe2x80x9cwhether or not there is available (hidden) data associated withxe2x80x9d the object). The method is limited in that data presentation is xe2x80x9cthree dimensionalxe2x80x9d only in the sense that it consists of three superimposed hierarchical flow charts.
Pirolli et al. (U.S. Pat. No. 5,835,905) and Pirolli et al. (U.S. Pat. No. 5,895,470) disclose a system for extracting and analyzing information from a collection of linked documents at a locality to enable categorization of documents and prediction of the relevance of documents to a focus document. This invention is limited to analyzing the relevance of linked entities (e.g., linked Web pages at a particular Web locality or site) to one or more selected entities and cannot be used to analyze the associations among unlinked documents. The invention requires that the raw data characterizing documents be extracted from the documents, including (1) topology (xe2x80x9clogical organization . . . as defined by linksxe2x80x9d) of documents at the locality, (2) usage flow and (3) interdocument similarity. In a preferred embodiment of the invention, documents in a locality are processed by a statistical content analysis (SCA) process to yield token (xe2x80x9cwordxe2x80x9d) statistics (e.g., word occurrence). A document vector is produced for each document, in which each element of the vector represents the presence or frequency of occurrence of a word in the document. For each pair of documents, a dot product of the document vectors is computed to produce the interdocument similarity measure. The invention calls for the documents to be categorized, preferably by function, into categories that the invention assumes are defined by a person. A technique called xe2x80x9cspreading activationxe2x80x9d is used to predict the relevance of any particular document at the locality to one or more focus point documents. The focus point documents may be specific document(s) or a prototype of a category. The system may be used to provide input to visualizations that are based on one or a few characteristics of the documents. The method is limited in that it does not provide an overall view of the conceptually-determined associative structure of the data set. It is also limited in that basing relevance criteria on past usage patterns discourages serendipitous discovery and conceptual browsing of a data set. Methods intrinsically different from the dual-scaling methods used by the present invention are used to produce the representation of associations in the data set.
Wolff (U.S. Pat. No. 5,847,708) discloses a sorting technique in which a computer interacts with a user to develop a spatial structure to represent information. Extensive pre-indexing of the target data set is required. Extensive interaction with the user of the method is required to produce a sorted, organized computer screen display of data items which meet the user""s criteria Similarity and distance metrics are computed among items in the target data set, based on a fixed set of feature metrics or characteristics, and the data set is presented to the user in this way. The user can then change the distance relationships among the displayed items to represent clusters of items that appear relevant to his or her needs. The method then queries the data set for a new set of data items based on the distance relationships specified by the user. The criteria used to judge similarity among data items is externally imposed, for example, dates of publication, rather than emanating from the conceptual nature of the data items themselves. A general limitation of most associative distance plots, such as the one produced by this method, is that the basis of the similarity measure or measures is implicit and implied, but not explicitly stated or revealed. The user of this method may be basing similarity judgments on a set of criteria which is quite different from the criteria for similarity imposed by the method itself
Rao et al. (U.S. Pat. No. 5,883,635) disclose a computer-implemented method of producing a single-image compressed view of a multi-image table by replacing the character image information in each cell of the multi-image table with a graphical representation of the information. The method is limited in that it cannot be used to illustrate associations among textual documents. The method provides a sequential, tabular view of multiple attribute measurements (xe2x80x9caveragexe2x80x9d, xe2x80x9ccareer averagexe2x80x9d, xe2x80x9csalaryxe2x80x9d), which have been translated into various standard visual representations appropriate to the data: bar graph, frequency graph, scatter plot, etc., all of which differ from the approach, object and form of the present invention.
Johnson et al. (U.S. Pat. No. 5,917,500) disclose an intellectual structure for displaying multi-dimensional data by representing it as a computer-generated model or plot of data in a parallel or non-orthogonal coordinate space. The data display facilitates relative motion of an observer with respect to the data. The invention cannot be used to display associations among documents in orthogonal Euclidian space. The method as described applies to the representation of continuous data in visual slices within a three-dimensional space, as opposed to the representation of discrete, categorized data in which the relationships between data items and category items are revealed, as is the case for the present invention.
Punch, III et al. (U.S. Pat. No. 5,924,105) disclose a method and product for generating a word set for use in locating documents having a type similar to a type of document in a document collection. The method involves selecting group of documents (i.e., grouping the documents into labeled categories), stemming the words in the documents to obtain stem words, determining a word count for each stem word in each document, clustering the stem words base on the word count of each stem word to obtain a word set. The invention is limited in that the selecting and category labeling step is performed by a user based on his/her individual preferences. The stemming step is accomplished by means of standard information retrieval techniques. A pattern matrix is developed with rows representing documents and columns representing individual features (word stems) and the feature values being the number of occurrences of the given word in the given document. In one embodiment, conventional feature selection methods, such as sequential forward selection, sequential floating feature selection and genetic algorithm searching may be used to improve the accuracy of the process of clustering features into groups with similar members. In a preferred embodiment, Hartigan""s K-means partitional clustering algorithm is used to look for similarities among column (word stem) vectors. The K-means algorithm is run several times with different random seeds in order to improve the performance of the method (i.e., increase confidence in the resulting clusters.) The resulting word set may be used to construct search engine queries. The K-means algorithm differs from the correspondence algorithms used in implementing the present invention.
Hilsenrath et al. (U.S. Pat. No. 5,926,812) disclose a computer-implemented method for comparing the contents of two sets of documents. The invention cannot be used to establish the associations among all documents in a collection. Corresponding sets of xe2x80x9cdocument extract entriesxe2x80x9d are extracted from each document set. Each extract entry comprises a weighted word histogram, i.e., a set of histogram word records. Each set comprises a word from the document, a word score (i.e., a measure of the importance of the word in the document), the number of appearances of the word in the document and a list of position indices for the word. Corresponding sets of word clusters are generated from the sets of document extract entries. Each word cluster comprises a cluster word list having N words, an Nxc3x97N total distance matrix and an Nxc3x97N number of connections matrix. Similar word clusters are grouped and combined to form a single word cluster for the group, but concepts are not extracted. The degree of similarity between clusters is determined by summing diagonal matrix elements, summing off-diagonal matrix elements and by summing all matrix elements. The method uses certain known characteristics of the sub-matrix partitioning of matrices which allow the data represented by those matrices to be sorted into subsets. Certain measures of the differences between those subsets are taken and used as a kind of metric profile which allows the retrieval of documents more or less matching the same profile. Therefore, it is a search and retrieval methodology, as opposed to one which reveals the conceptual context of the data set. The object of the methodology is to return data relevant to the user, not to facilitate the understanding conceptual relationships within the data set.
Non-patent sources of information known to be relevant to the present invention include several academic papers regarding the application of dual-scaling methods, primarily correspondence analysis, to market research. The origins of correspondence analysis, which is a geometric approach to multivariate descriptive analysis, go back to at least the 1930s, and it has been known by various names including dual scaling, reciprocal averaging, homogeneity analysis, and canonical scoring. The basic methodology is typically used for qualitative exploratory data analysis. In the United States, researchers and statisticians such as Hoffman and Franke (1986) and Carroll, et al. (1986, 1987) published discussions of the mathematics involved in correspondence analysis in the context of its application to market research. The basic techniques have also been applied to research in the social sciences. The following is a list of academic background sources for mathematical algorithms used as part of the methodology of the present invention:
Hoffman, D. L. and Franke, G. R. (1986) in Correspondence Analysis: Graphical Representation of Categorical Data in Marketing Research, Journal of Marketing Research, 23, pp. 213-227, describe how to apply correspondence analysis to categorical data obtained in marketing research.
Carroll, J. D., Green, P. E. and Schaffer, C. M. (1986) in Interpoint Distance Comparisons in Correspondence Analysis, Journal of Marketing Research, 23, pp.271-280, describes the conditions under which squared interpoint distances (particularly between-set differences) can be compared in correspondence analysis of marketing research data.
Carroll, J. D., Green, P. E. and Schaffer, C. M. (1987) in Comparing Interpoint Distances in Correspondence Analysis: A Clarification, Journal of Marketing Research, 24, pp.445-450, describe conceptual and empirical differences among scaling options in correspondence analysis.
Hoffman, D. L., de Leeuw, J. and Arjunji, R. V. (1994) in Multiple Correspondence Analysis in R. Bagozzi (Ed.), Advanced Methods of Marketing Research, pp. 260-294, Malden, Massachusetts: Blackwell Publishers Inc. describe using multiple correspondence analysis techniques to illustrate similarities and dissimilarities among brands with respect to variables describing the brands.
The discussions and examples used in each of the papers referenced above are based on survey or other data collection documents which must be manually completed by a group of subjects. Such data collection instruments typically consist of a table in which the pre-defined data items of interest, for example, companies or brand names, are listed in the column positions, and a pre-defined set of attributes or categories, for example, xe2x80x9creliabilityxe2x80x9d, xe2x80x9ccustomer responsexe2x80x9d, xe2x80x9cmanufacturingxe2x80x9d, etc., are listed in the row positions. Subjects are instructed to indicate in the table, using a pre-defined scale, how they rate each of the data items in regard to each of the attributes. A summation table of all subjects responses is used for input to a dual-scaling operation. It is apparent that each of the papers referenced above is limited in that it assumes a set of pre-defined attributes or categories by which subjects can rate each data item, and each relies on a human subject or subjects to perform the rating. Unlike the present invention, none of the above references are concerned with exploring inherent and self-described conceptual relationships among items in a data set, and none provide or suggest a method by which such an exploration could be accomplished in an automated fashion using dual-scaling algorithms.
Other known non-patent and non-academic sources with some relevance to the present invention include the following:
Rao, R. and Sprague, Jr., R. H. (1998) in Natural Technologies for Knowledge Work: Information Visualization and Knowledge Extraction in Journal of Knowledge Management, 2(2), pp. 1-14. This article is a survey describing various recent information visualization techniques, such as the Perspective Wall, the Cone Tree and the Hyperbolic Tree. The article also includes discussions of a variety of linguistic processing functions, such as tokenizing, stemming, tagging and phase extraction. The reference is limited in that none of the described visualization techniques, which include hierarchical display structures, nodal display structures, a three-dimensional xe2x80x9cperspective wallxe2x80x9d with item types displayed on the wall, and xe2x80x9csmall-multiplesxe2x80x9d types of tabular displays, resemble or offer the advantages of those of the proposed invention in terms of visual structure or in terms of objectives.
In regard to the discussed linguistic processing techniques, two of them, elimination of xe2x80x9cnoisexe2x80x9d words, and xe2x80x9cstemmingxe2x80x9d, are relevant to the present invention. Noise words are simply words which are to be disregarded in a content or structure analysis. No related art reference, however, eliminates from consideration as xe2x80x9cConceptsxe2x80x9d (as that term is used in the present invention) of noise words consisting of articles of speech, forms of the verb xe2x80x9cto bexe2x80x9d, all words less than three characters in length, and so on. Moreover, in none of the above references, is a method disclosed in which users are able to further define the set of noise words to include various parts of speech, such as all adverbs, as well as specific words or terms to be ignored in the analysis, the latter including even Concept terms, as is the case in preferred embodiments of the subject invention.
The present invention also makes use of a technique somewhat analogous to stemming, but stemming is quite different in concept and, in terms of the present invention, quite different and limited in effect. In the related art, xe2x80x9cstemmingxe2x80x9d is the reduction of various grammatical forms of a word to some common form through the use of an algorithm which modifies or removes the word endings. The resulting common form is not necessarily correctly spelled: for example, the typical stemming algorithm reduces xe2x80x9ccomputerxe2x80x9d, xe2x80x9ccomputersxe2x80x9d, xe2x80x9ccomputingxe2x80x9d, and xe2x80x9ccomputationxe2x80x9d to the common form xe2x80x9ccomputxe2x80x9d. Common methods of stemming available in the related art are limited in that they are not particularly useful for identifying root Concepts, which is an object of the present invention, or for displaying them in a visual plot since the common stem word is frequently misspelled. In no combination of related art references are various grammatical forms of words in Entity descriptions reduced to grammatically correct words representing the root concepts on which those word forms are based, as is the case with the present invention. Typically, in the present invention, this is the noun form of a given word: xe2x80x9ccomputingxe2x80x9d and. xe2x80x9ccomputexe2x80x9d, for example, become xe2x80x9ccomputationxe2x80x9d, while xe2x80x9ccomputersxe2x80x9d and xe2x80x9ccomputerxe2x80x9d become xe2x80x9ccomputerxe2x80x9d. Such translations are made prior to the step of identifying Concepts. In this manner, the strengths of associations between Entities are based on fundamental and underlying conceptual similarities between them, which is not the case with related art methods.
In a February, 1999, article by George Lawton, (Lawton, G. (1999) in Building the New Knowledge Interface, Knowledge Management), the author writes of a conversation with Jim Blair, a research director with the Gartner group, in which Blair envisions in the future a three-dimensional environment (a xe2x80x9cstar mapxe2x80x9d) displaying information which might resemble galaxies, solar systems, planets, and moons. When a user searches for information, he gets back not a list of items, but a planetarium view which shows the relationships between the various documents. Those skilled in the art of clustering techniques used in market research and in the social sciences note the visual analogy between xe2x80x9ccluster mapsxe2x80x9d and xe2x80x9cstar maps.xe2x80x9d The purpose of cluster maps, as discussed throughout this document, is to reveal relationships between objects in the visual plot: the techniques for doing so are well known and are not new. Related art references are limited in that in no instance are the measures of similarity, or Concepts, extracted from the data set itself. Furthermore, no references disclose an effective methodology for using Concepts to measure the strength of association and relationship between data Entities, and effective methodology for displaying Concepts in relationship to the data Entities. Thus, no discussion or speculation in the Lawton (1999) article suggests the methods or the results of the present invention. Furthermore, the first experimental prototype reducing the present invention to practice was built and operational before the Lawton (1999) article appeared in print.
In all likelihood, the use of three-dimensional computer simulation, as well as in the notion of displaying information within such a space and being able to navigate through it, will continue to increase in popularity. There are a multiplicity of ways to combine these two factors, but the methods for doing so can differ widely in terms of purpose and in terms of the nature and usefulness of the information they convey. For example, the following quote was taken from the San Francisco Chronicle business section, Feb. 18, 1999, in a story concerning the rollout of a new three-dimensional chip made by Intel:
xe2x80x9cThe Pentium III represents a great leap forward in using three-dimensional technology.
Intel demonstrated some examples, including a search on the Excite Internet directory that served up results looking like satellites orbiting small planets.xe2x80x9d
A phone call to the reporter and a check with a spokesperson at Excite, Inc., revealed the demo was a soon-to-be-released product named Excite Extreme. The xe2x80x9cplanetsxe2x80x9d around which xe2x80x9csatellitesxe2x80x9d orbit are standard high-level Excite search categories such as xe2x80x9cSportsxe2x80x9d, xe2x80x9cWeatherxe2x80x9d, xe2x80x9cBusinessxe2x80x9d, etc. The satellites are Web sites returned by a user""s query, and they orbit in an animated fashion around their respective categories. The methodology disclosed in this reference is limited in that the data set is made to fit a predetermined set of categories, with the categories being placed in predetermined locations in the attribute space, rather than allowing the data set to determine the shape of its own space based on its inherent conceptual characteristics. Even if the display were based on a variation of the dual-scaling methods previously discussed (which is not suggested by the related art), the somewhat gratuitous orbiting of data objects around category objects would serve only to eliminate the possibility of perceiving distance-based relationships among objects in different categories. Such a presentation is limited in that it does not address the common situation in which objects belong to multiple categories, including the common situation in which an object belongs very much to one category but not so much to another. The disclosed presentation method is further limited in that it does not convey information about the relationship of the categories to each other, e.g., xe2x80x9cWhat is the relationship of xe2x80x9cSportsxe2x80x9d to xe2x80x9cWeatherxe2x80x9d or xe2x80x9cBusinessxe2x80x9d in the context of the current data set?xe2x80x9d Thus, the methods used by Excite Extreme for formulating the attribute categories (xe2x80x9cplanetsxe2x80x9d) as well as for displaying the associative relationships between attributes and data items in a three-dimensional space are, thus, substantially different from and limited in comparison to those described in the present invention.
The Pacific Northwest National Laboratory (PNNL) has posted information about a variety of its proprietary information visualization technologies on a website entitled, xe2x80x9cSPIRxe2x80x94Spatial Paradigm for Information Retrieval and Exploration.xe2x80x9d SPIR was apparently developed in secret for the U.S. intelligence community. Aspects of the SPIR technology have been commercialized by Cartia, Inc. and maps produced using the technology are illustrated on its websites at the domains cartia.com and newsmaps.com. These references are limited because the process used to produce the maps is not disclosed and cannot be determined by examining the maps. Koprowski, G. in New Markets Plugged In, Nov. 9, 1995, reported that one of the SPIR visualization engines, named Galaxies, uses xe2x80x9cprincipal components analysis algorithmsxe2x80x9d to xe2x80x9cidentity potential axes with the highest information content,xe2x80x9d but how this is done is not disclosed. Thus, the discussion of these references presented herein is a conjecture.
SPIR-related technologies are limited in that they appear to rely, in an initial text processing step, on an analysis of the context of terms in documents to ascertain their meaning and on a measurement of the frequency of occurrence of terms in different documents to give weight to a similarity measure. The approach of analyzing and weighting the probable meaning of ambiguous words in documents is costly in terms of processing, error prone, and not necessary to produce a meaningful relational map of an information space. It is much more efficient to use the relationships between all root terms and entities in a data set to differentiate the intended meaning of ambiguous terms.
It appears that SPIR-related methods rely on methodologies that require input of an Nxc3x97N matrix of data items by data items, as opposed to a smaller and more efficient Nxc3x97M matrix of data items by categories. This is a serious limitation because the statistical algorithm is required to process a much larger volume of data. Nxc3x97N matrices expand very quickly, as (N*N)+N/2 entries are needed to produce a contingency matrix for the data items. These methods are also limited because the xe2x80x9cthemesxe2x80x9d used to generate the values in each element of the matrix are represented implicitly and indirectly by the vectors formed by dense groupings of data items in the space, possibly by means of a principal components analysis.
Some SPIR-related technologies use an essentially two-dimensional xe2x80x9ctopographic mapxe2x80x9d display in which peaks are rendered to appear to be higher than valleys, with peaks representing concentrations of documents with similar xe2x80x9cthemes.xe2x80x9d This approach is limited in that it does not make use of the third dimension, i.e., the z-axis, to provide an efficient context in which to differentiate relationships of objects in the space. It may be that a form of cluster analysis is used to produce the groupings, which are rendered as irregular shaded areas on the topographic map and that the groups are labeled using an undisclosed method of extracting themes from text. The technology is limited in that it handles the problem of themes that span more than one data item group by repeating the label of the theme in each data group with which it is associated. This approach is less effective than representing each concept object as a single point, more or less equidistant from all the data objects it is related to, unless some other strong relationship(s) skew the data objects in a particular direction. In fact, maps produced with SPIR-related technologies appear to have no individual points which represent concepts. Thus, these methods do not plot Euclidean distances between concepts in three dimensions, which has great value in the present invention, and, hence, appear to use a basically different and less effective approach to displaying information about items in data sets.
The foregoing review of related art shows that many problems in the area of information overload have not been solved by developments in the related art. In summary, the limitations, deficiencies and disadvantages of related art methods for representing conceptual and relational structure in data sets are as follows:
Most of the references require pre-processing of the targeted data sets, which is required to produce a referent structure that can then be searched for relevant information. Such pre-processing relies on a set of predetermined categories or characteristics, such as xe2x80x9crestaurants,xe2x80x9d or a predetermined metric, which is used to organize the data. Various sophisticated pre-processing statistical techniques are employed by the referenced examples, but any methodological requirement that the target data set be pre-indexed or pre-processed is problematic in terms of processing overhead involved and in terms of maintenance of the target data set as it grows and changes.
Most of the referenced methods focus on matching the pre-processed data set structures to search queries, or criteria, or xe2x80x9cprofilesxe2x80x9d, supplied by the user. Data are then located in the pre-processed data set which matches the search criteria. This approach is counterproductive in certain situations in which the search criteria are not exact. For example, if one remembers a restaurant as being Italian when, if fact, it is Greek. In this instance, one would prefer the candidate data set to include items which are in some way associated to the query terms, though the match may be inexact. It will be noted that some of the referenced search and retrieval methods do return a kind of xe2x80x9cfuzzyxe2x80x9d data subset, but, again, these similarity relationships are based on eternally-imposed criteria or metrics rather than on concepts inherent in the data itself What is preferred is a means of displaying conceptual relationships within targeted data sets based on the associated concepts and instances within those same data sets. This is not accomplished by related art methodologies.
An advantage of using clustering techniques to view data sets is that such techniques reveal groups of similar items. Like categorization, the grouping of items facilitates understanding of the meaning of those items within the data set. As previously discussed, formulating meaningful category labels for groups of data items is a laborious and error-prone process usually requiring human interpretation and/or human intervention. Human interpretation without human intervention, for example, in an automated context, invites incompleteness and error. Human intervention is generally unsupportable in real-time situations, and is very processing expensive in situations in which the data set is amorphous, growing, and changing, for example, the World Wide Web. Therefore, it is not surprising that none of the methods in the related art references attempt to extract or identify categories, and display them as such, in real time. What is needed, ideally, is a method which allows the items in the target data set, whatever that is, to categorize themselves based on their content. In other words, what is needed is a means of allowing the words within the data set to self-describe their context and their interrelated associations.
A similarity matrix is used as input to most clustering techniques. This can be envisioned as a table in which data items are represented in the table""s columns and some attribute or attributes on which the data items will be rated are represented in the rows of the table. In the intersecting element of each column and row is a value rating the data item in that column according to the attribute in that row. The attributes can be almost any type of measurements, but attributes that make intuitive sense in terms of the data set produce more intuitive graphical plots. The metrics which the related art references use to generate similarity measurements between data items are often abstract, for example, the frequency-of-use in the English language of various data words, or a measure of word-difficulty, or a measure of word proximity to other words in a document. Many combinations of these and attributes have been used to produce measures of association. These measures can be used to produce plots of the data set in which similarly judged items cluster together. Such measures fall short of explaining the associations between data items in terms of the actual conceptual and semantic relationships among them, however. The observer knows that certain items are more related to each other than to other items, but the metric which produced the clustering, word frequency for example, is an abstract and somewhat artificial measure of that similarity, which tells one little about the meaning of the clustered items. What is needed is a method of obtaining measurement attributes that are conceptually related to the data items themselves.
An invention which could extract categorical information on-the-fly from a data set, which could use those categories to form measurements of similarity among the data items, and could then plot those data items in a visual space, would still be deficient if the extracted categories themselves could not be displayed in a way that clearly illustrates their relationships to the data items. The methods of the related art references are not capable of displaying a dual representation of the data items and the concepts which bind them together, or of the relationships between the two sets, with the result that a considerable amount of important information is missing, or must be inferred, from the plot. In one of the related art references, the search criteria which produce a data subset which is displayed in a data plot are represented as axes projected through the data space. However, given that the user already knows what his or her search criteria are, this approach does not add particular value in the sense of being able to understand the implicit conceptual and contextual structure of the data set. In that respect, what is needed is a method in which (a) the measurement attributes used to rate the data items are extracted from the content of the data items themselves, and (b) the measurement attributes are also displayed as individual items in a graph along with the data items in such a way as to provide conceptual and categorical labels for the data items and data item clusters. This type of exploratory context invites and facilitates the exercise of the user""s subjective judgment of the potential relevance of items in the data set, and provides the user with the ability to discover new relationships in the data of which he was not previously aware.
Lastly, the graphical display of data and concept relationships in a visual space benefits from current and common computer graphic simulation technologies. For Euclidean distance plots, the benefits of such technology over a static printed image are obvious, not the least of which being that the Euclidean solution space can be represented in three dimensions, and the viewer can navigate through the space at will in any way desired. This is particularly useful for Euclidean plots of the type discussed here, because the viewer can move toward closely joined objects and around occluded objects in the data space to view them from better perspectives. The ability to view relationships in the data set from a multitude of angles and perspectives facilitates more complex understanding of those relationships. A few of the methodologies previously referenced use and make note of the advantages of three-dimensional representation in simulated computer space. None of them, however, employ such an approach to produce the type of visual representation which would solve the problems disclosed here.
A person skilled in the art will note that the referenced related art does not solve these problems, and it will become clear that they do not teach the present invention""s system and method for extracting inherent and implicit conceptual relationships and semantic associations existing among items in a data set, or for representing those associations in simulated three-dimensional space. Thus, no combination of related art explicitly or implicitly suggests the elements or steps of the present invention.
The present invention is a system and method which overcomes the information overload problems identified above. The present invention is concerned with the extraction of implicit conceptual information from items in data sets, the subsequent extraction of conceptually-based associative information among items in data sets, and the subsequent representation of those relationships within a visual space. Terms comprising such associative information need not be, and in the main are not, specified by the human operator of the invention: rather such terms are culled from descriptions of the data items themselves.
Preferred embodiments of the invention rely upon xe2x80x9cdual-scalingxe2x80x9d algorithms, methods, techniques or approaches whose output comprises a simultaneous (or dual) plot of objects represented in the rows and columns of a frequency or contingency table, displayed as points in a low-dimensional space. A preferred approach to dual scaling is correspondence analysis, which has also been called a geometric approach to multivariate descriptive analysis, canonical analysis of contingency tables, categorical discriminant analysis, homogeneity analysis, quantification of qualitative data, and simultaneous linear regression. Correspondence analysis has advantages in term of simplicity, efficiency, and non-restrictive assumptions regarding data input, but the methods and systems disclosed herein rely on any of a number of methods that result in simultaneous row and column display of contingency table data in a Euclidean space.
Preferred embodiments of the present invention offers the following advantages and advances over other methods referenced in the background art:
The present invention is not computationally complex, therefore its processing overhead is low. Extensive pre-processing or pre-indexing of the target data set is not required. The current invention calculates associations in the data set on-the-fly.
A xe2x80x9cuser profilexe2x80x9d, xe2x80x9cinput profilexe2x80x9d, xe2x80x9cvector profilexe2x80x9d or other type of criteria input is not required for the operation of the invention, nor does the invention require a supporting database.
Input data requirements are simple, and the input can come from an almost unending variety of sources. The only data requirements consist of (a) a name of a data item, and (b) any kind of description of that item.
The attribute items used as similarity measures are generated directly from words from the descriptions of the data items themselves, so they are relevant to the data set by definition. No interpretation or translation of word meaning is required.
The present invention reveals hidden and implicit information about the conceptual nature of the data items and about the conceptual structure of the data set itself
The strengths of associations between the categories or attribute items used as measures of similarity are also plotted as Euclidean distances in the graph, along with the data items.
The present invention reveals strengths of association between clusters of data objects and clusters of attribute objects, as well as between individual objects. It also reveals overlapping conceptual and categorical regions in the data space.
The present invention provides a whole-field, simultaneous display of the target data set. The three-dimensional graphics and movement simulation provide detailed views of the data space and allow the observer to look around and behind objects that may be occluding other objects in the data space.
A preferred embodiment of the invention accepts raw input data in the format of Entity: Description pairs (name-description pairs or label-description pairs), extracts Concepts (conceptual information or measurements of attributes), which are the term- or word-based associations implicit in each Entity""s description, and uses Concept terms to reveal a relational structure (or associative relationships) among data items which is based on the associative strength between Entities in the data set, between Concepts in the data set and between Concepts and Entities in the data set. This associative structure is displayed in terms of a dual-scaled map, that is, a simultaneous display of both Entities and the Concepts which have been used to associate them as points or virtual objects projected into a computer-simulated three-dimensional space. Viewers can access Descriptions for each Entity by activating that Entity in the visual space, e.g., with a mouse click. Entity Descriptions can include text data, hyperlinks and Uniform Resource Locator (URL) links to original data sources represented by the Entities, or any other electronically-presentable type of data associated with the Entity. When the viewer selects a Concept object in the visual space, the corresponding Entity objects associated with that Concept are highlighted. Conversely, selecting an Entity item in the visual space highlights the associated Concepts. The viewer can select relevant Entities to be retained and included in a subsequent raw data input set which can be re-submitted to the methods of the invention. Viewers are able to fine-tune the process in a number of ways. Various encapsulation and summarization methods are available for simplifying very large or dense data displays.
Preferred embodiments of the invention can use an unlimited variety of target data sets which can be manipulated in a variety of ways to provide data input. A target data site might consist of a subset of World Wide Web sites returned by a conventional search engine used to search for a particular term or combination of terms. In this particular case, Entities would consist of the names the returned Web sites and/or their URLs, Descriptions would consist of a composite of KEYWORD, DESCRIPTION, and META fields from the H.IL representations of the Web sites content, and Concepts would be extracted from the Descriptions of those sites.
Target data sets can easily come from conventional database sources, such as the one maintained by the United States Patent Office. In this particular case, a standard search might conducted on the database and a set of patents returned which meet the search criteria. In that particular subset, Entities would be consist of the titles of the patents, or their numbers, or the names of the inventors. Descriptions could be drawn from the summary, abstract, or description sections of the patent application, or a combination of any of these. Concepts would then be extracted from the Descriptions. A working example very similar to this is referenced later in this document.
A myriad of other data sources, such as personnel databases, medical and law databases, specialized databases of all types whether structured or unstructured, can be rather easily tapped for input into the methods of the current invention. Any text source, such as news publications, works of literature, and periodicals, can be used for input to the current invention. Thus, preferred embodiments of the invention are applicable to data sets obtained by querying databases (e.g., relational and object), flat files and text. A working example is disclosed below in which the Business section of the New York Times was used as the target data set.
Preferred embodiments of the invention involve extracting Concepts from Entity descriptions in a variety of ways. One such embodiment identifies linguistic root terms from terms in Entity descriptions and use one or more said root terms as Concepts. In this embodiment, non-noise terms in Descriptions are reduced to their most common root form, and root terms become Concepts if they are associated with two or more Entities. The user of the system can control the Concept extraction process by specifying various characteristics to use in identifying which description terms can be tagged as Concepts. The user can also control the density of Concept extraction from a given data set.
Another embodiment involves using a computer-implemented thesaurus or other word corpus to refine the process of extraction of Concepts by identifying and eliminating synonyms among root terms. Another embodiment involves the selection of Concepts from a standardized vocabulary, such as a vocabulary of medical terms, job descriptions in a personnel database, etc. Various criteria can be used to select root terms to be used as Concepts in the scaling operations inherent in the present invention. No restriction on the methodology used to identify Concepts from Entity descriptions is hereby implied.
Preferred embodiments of the invention involve quantifying the associative structure among Entities and Concepts in a variety of ways. Quantification of associative structure is accomplished by processing matrices, tabulations, contingency, or similarity tables of Entity/Concept data using a dual-scaling algorithm or algorithms which are capable of producing dual-scaled plots in Euclidean space of both the row and column items in such a table or matrix. A list of such dual-scaling algorithms or techniques includes but is not limited to: nonlinear multivariate analysis, correspondence analysis, multiple correspondence analysis, multidimensional scaling, reciprocal averaging, homogeneity analysis, and canonical scoring.
Preferred embodiments of the invention are capable of using, but not limited to, non-symmetrical tabular matrices containing binary data in order to produce the resulting dual-scaled plot of Entity and Concept objects.
Preferred embodiments of the invention allow users to specify the type of dual-scaling algorithm to be used to calculate relative Euclidean distances between pairs of Entity objects and between pairs of Concept objects. The user can also specify row-centroid, column-centroid, or row-column-centroid symmetric approaches to the calculations used to produce the Entity and Concept display.
Preferred embodiments of the invention allow users to specify the granularity of the Concept display: e.g., to specify that the same root term must be found in 25 percent, 50 percent, or 75 percent, and so on, of the Entity descriptions in order to be displayed as a Concept. This is one method for facilitating a generalization and simplification of very dense displays.
Preferred embodiments of the invention allow users to adjust the sizes of the visually plotted Entity and Concept objects relative to their positions. This has the effect of expanding or contracting the relative distances of objects from one another in the visual data space and provides one way to adjust the visual clarity of and generality of dense data sets.
In addition to displaying relative strengths of associations in terms of chi-square or Euclidean distances in the visual space, preferred embodiments of the invention also explicitly display the relationships between Entity and Concept items, in that when users select Concept objects in the visual space their corresponding associated Entity objects are visually highlighted, and/or listed. Likewise, when users select Entity objects in the visual space, the corresponding Concepts objects are highlighted or listed.
Preferred embodiments of the invention utilize grouping techniques including mathematical operations such as, but not limited to, cluster analysis, factor analysis and principal components analysis, for the purpose of generalizing and simplifying the data display produced from the results of the dual-scaling algorithm. Cluster analysis and like techniques are used to group individual objects in a data space into N number of mathematically distinct clusters. Thus, they are used in some of the methods and systems disclosed herein to group similarly positioned objects in Euclidean space and to provide zoom-in, zoom-out kinds of views of whole data space. Other ways to group data objects in the display space are also envisioned, e.g., groups defined by a spreading linkage of shared concepts.
The preferred embodiment of the invention can then visually reduce individual data items within such a cluster to one encapsulated object or icon representing all the individual data points within that cluster. A combined list of Concepts within such a cluster provides an auto-categorization for the encapsulated object. The reduced representation of the data cluster can also be unfolded into its individual constituent objects, providing another way to control and adjust the density or complexity of a given visual data display. The procedure can be repeatedly used on a given data set to provide drill-down and drill-up views of a data set.
The present invention exhibits a number of advantages over the related art. Among the advantages of preferred embodiments of the present invention are the following:
The relationships between all Entities and all Concepts are plotted in a simulated three-dimensional visual space such that the relative distances between all points in the space, both Concepts and Entities, can be interpreted as measures of strength or weakness of association. In general, the closer together two items are plotted in the map, the stronger their presumed association; while the further apart they are in the map, the weaker their association.
The displayed relational structure among the data items is based upon inherent characteristics of the data items themselves, said characteristics being identified and displayed without user intervention in such a way that their contribution to the total relational structure is apparent. In this way, the invention involves extraction from the content of the item descriptions the measurement attributes used to assess the relationships among the items.
The method uses the associative structure found between all of the Concept terms associated with each Entity, and their relationships to all other Concepts, to clarify distinctions between Entities that might otherwise be ambiguous or misleading.
The resulting displayed map facilitates the user""s cognitive orientation to the entire field of data and subsequent recognition of items and areas of the map that are pertinent to the user""s subjective intentions. This directly addresses a problem that arises as a corollary to advances in information technology, which is the cognitive difficulty of processing large amounts of information with little context or relational structure.
The resulting map allows immediate access to the data sources represented by the Entities in the map.
In broad terms, a preferred embodiment of the invention includes using nonlinear multivariate analysis, correspondence analysis, multiple correspondence analysis, dual scaling, multidimensional scaling, reciprocal averaging, homogeneity analysis, or canonical scoring algorithms to reveal associations among documents in a given document set.
In broad terms, a preferred embodiment of the invention is also a method for extracting inherent and implicit conceptual relationships and semantic associations existing among items in a data set, and for representing those associations in a simulated three-dimensional space, said method comprising the steps of:
organizing said items into a plurality of data pairs, each data pair comprising an entity label and a textual or symbolic description of the entity;
creating a modified set of entity descriptions by pruning irrelevant terms from entity description lists and reducing each remaining term to a linguistic root form;
extracting concepts from said modified description set, each concept comprising a root term that appears in at least two modified descriptions of at least two entities;
producing a similarity matrix wherein each entity is represented as a column item in said matrix and each concept is represented as a row item, or vise versa, the element of each such column and row pair containing a binary indication of whether the corresponding concept is present in the corresponding entity""s modified description list;
quantifying the associative structure of the data set by subjecting the similarity matrix to procedures comprising a statistical method known as correspondence analysis, in combination with auxiliary matrix transformation operations described herein, thereby producing a set of coordinates for each concept and each entity in a computer-simulated, multi-dimensional Euclidean space; and
displaying the concepts as one type of virtual object and the entities as another type of virtual object with each object located at the appropriate coordinates in the multi-dimensional space, wherein the relative distances among the concept objects reflect the degree to which the concepts are associated with one another, wherein the relative distances among the entity objects reflect the degree to which the entities are associated with one another and wherein the relative distance between each concept object and each entity object reflects the degree to which each entity is associated with each concept.
In a preferred embodiment, the method also comprises allowing the viewer to adjust the granularity of the concept extraction process and the density of the concept and entity display, as well as the scaling method to be used in the analysis.
In broad terms, a preferred embodiment of the invention is also a system for identifying and displaying inherent semantic constructs in a data set, such as one comprised of a plurality of World Wide Web sites or pages and their descriptions, said constructs which are held in common by more than one entity of said data set, in a manner such that the strength of semantic association between all data entities and identified concepts are represented as visually-observable distances between data points in an n-dimensional Euclidean space, said system comprising:
a network of computers, said network comprising interconnected server computers and client computers, some of said server computers storing and serving web sites having contents,
means for producing a data set residing in said network, said data set comprising a plurality of data pairs, each data pair comprising a label for a web site and a textual or symbolic description of the web site;
means for creating a modified set of web site descriptions by pruning irrelevant terms from web site description lists and reducing each remaining term to a linguistic root form;
means for extracting concepts from said descriptions residing in said network, each concept comprising a root term that appears in more than one description;
means for producing a similarity matrix residing in said network, wherein each web site ts is represented as a column and each concept is represented as a row or vise versa, the element of each such column and row containing a binary indication of whether the concept is found in the corresponding web site""s modified description list;
means for quantifying the associative structure of the data set by subjecting the similarity matrix to means for correspondence analysis in combination with auxiliary matrix transformation operations residing in said network, thereby producing the coordinates of each concept and each web site in a multi-dimensional Euclidean space; and
means for displaying the concepts as one type of virtual object and the web sites as another type of virtual object with each object located at the appropriate coordinates in the multidimensional space, said means for displaying residing in a client computer, wherein the distances among the concept objects reflect the degree to which the concepts are associated with one another, wherein the distances among the entity objects reflect the degree to which the entities are associated with one another and wherein the distance between each concept object and each web site object reflects the degree to which the content of each web site is associated with each concept.
The invention can be applied to a data source on an intranet, for example, the U.S. Patent Office""s patent database. And/or, it can be embedded in a Help system, like Microsoft Help, as an alternative way to view the data store of Help topics, or subsets thereof
In broad terms, a preferred embodiment of the invention is a computer-readable medium having stored thereon sequences of instructions which when executed by a processor cause the processor to perform the steps of:
acquiring a data set comprised of items;
organizing the items into a plurality of data pairs, each data pair comprising an entity and a description of the entity;
creating a modified set of entity descriptions by pruning irrelevant terms from entity description lists and reducing each remaining term to a linguistic root form;
extracting concepts from said modified description set, each concept comprising a root term that appears in more than one modified description;
producing a contingency matrix wherein each entity is a column and each concept is a row or vise versa, the element of each such column and row containing a binary indication of whether the concept is found in the entity description;
quantifying the associative structure of the data set by manipulating the contingency matrix as follows:
collapsing identical row profiles and combining the concept terms associated with each into a single complex term,
subjecting the contingency matrix to singular value decomposition and other mathematical operations to produce an n-dimensional representation of the contingency matrix in Euclidean space, and
scaling said raw coordinates to produce coordinates of each concept and each entity usable in a given computer-simulated, three-dimensional space; and
displaying the concepts as one type of virtual object and the entities as another type of virtual object on said monitor or projection device with each object located at the appropriate coordinates in the three-dimensional space, wherein the relative distances among the concept objects reflect the degree to which the concepts are associated with one another, wherein the relative distances among the entity objects reflect the degree to which the entities are associated with one another and wherein the relative distance between each concept object and each entity object reflects the degree to which each entity is associated with each concept.
In a preferred embodiment, the invention is a computer-readable medium having stored thereon sequences of instructions which, when executed by a processor, cause the processor to perform the steps of a method disclosed herein. The computer-readable medium may be a disk, a CD-ROM, a tape, a hard drive or any conventional medium. In an alternative embodiment, a preferred embodiment of the invention is a method for operating a server computer, the server computer having a computer-readable medium having stored thereon sequences of instructions which may be executed by a processor, said method comprising serving to a client computer having said processor the sequences of instructions that cause said processor to perform the steps of a method disclosed herein.
A preferred embodiment of the invention is also a business method that involves the step of displaying to a user in a visual display implicit associations among a plurality of items in a loosely-structured data set in accordance with a method disclosed herein and the step of generating a billing charge producing business income from the displaying step. Business income is generated by obtaining the identity of said user (by means of information obtained from a cookie, form or credit card company) and charging the user for the privilege of viewing the display, by charging advertisers for posting advertisements within or in proximity to said visual display, by charging users a subscription or licensing fee in exchange for granting the user access to the display over a period of time or at a certain frequency, by licensing the invention to those in the business of organizing or presenting data sets, or by conventional means.